from typing import List


class TreeNode:
    def __init__(self, val: int):
        self.left = None
        self.right = None
        self.val = val


def buildTree(input: List[int]) -> TreeNode:
    nodes = [TreeNode(x) for x in input]
    for i in range(1, len(input)):
        if input[i] is None:
            continue
        parent = (i + 1) // 2 - 1
        if i % 2 == 1:
            nodes[parent].left = nodes[i]
        else:
            nodes[parent].right = nodes[i]
    return nodes[0]


def path_sum_3(root, target):
    prefix_freq = {0: 1}

    def helper(cur_node, pre_sum):
        nonlocal target
        if not cur_node: return 0
        cur_sum = pre_sum + cur_node.val
        path_no = prefix_freq.get(cur_sum - target, 0)
        prefix_freq[cur_sum] = prefix_freq.get(cur_sum, 0) + 1
        count = path_no + helper(cur_node.left, cur_sum) + helper(cur_node.right, cur_sum)
        prefix_freq[cur_sum] -= 1
        return count

    count = helper(root, 0)
    return count


print(path_sum_3(buildTree([10, 5, -3, 3, 2, None, 11, 3, -2, None, 1]), 8))
